×

A note on orientation and chromatic number of graphs. (English) Zbl 1390.05078

Let \(G\) be a simple and finite graph, and let \(D\) be an orientation of \(G\). If \(D\) has a directed path of order \(k\), then define \(\Delta_k(D)\) to be the maximum value \(t\) for which a directed path \(v_1\dots v_k\) in \(D\) satisfies that the outdegree of \(v_k\) in \(D\) is \(t\); otherwise, define \(\Delta_k(D)\) to be zero. The author of this paper mainly shows first that if \(D\) is an orientation of \(G\) such that the number of Eulerian subgraphs of \(D\) of an even size is not the same as that of an odd size, then \(\chi(G)\leq \Delta_k(D)+k\). Secondly, the author shows that for any orientation \(D\) of \(G\), \(\chi(G)\leq 2\Delta_k(D)+k\). In addition, the author also provides a relation between \(\Delta_k(D)\) and vertex partitions of a graph into degenerate subgraphs.

MSC:

05C15 Coloring of graphs and hypergraphs
05C20 Directed graphs (digraphs), tournaments
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon N, Tarsi M (1992) Colorings and orientations of graphs. Combinatorica 12:125-134 · Zbl 0756.05049
[2] Barbosa VC, Szwarcfiter JL (1999) Generating all the acyclic orientations of an undirected graph. Inf Process Lett 72:71-74 · Zbl 1339.05379
[3] Deming RW (1979) Acyclic orientations of a graph and chromatic and independence numbers. J Comb Theory Ser B 26:101-110 · Zbl 0331.05110
[4] Figueiredo RMV, Barbosa VC, Maculan N, de Souza CC (2008) Acyclic orientations with path constraints. RAIRO Oper Res 42:455-467 · Zbl 1198.90336
[5] Gallai T (1968) On directed paths and circuits. In: Erdős P, Katona G (eds) Theory of Graphs, Proc. Tihany 1966. Academic Press, New York, pp 115-118 · Zbl 1184.05029
[6] Jensen TR, Toft B (1995) Graph coloring problems. Wiley, New York · Zbl 0855.05054
[7] Kawarabayashi K, Thomassen C (2009) Decomposing a planar graph of girth \[55\] into an independent set and a forest. J Comb Theory Ser B 99:674-684 · Zbl 1184.05029
[8] Richardson M (1953) Solutions of irreflexive relations. Ann of Math 58:573-580 · Zbl 0053.02902
[9] Roy B (1967) Nombre chromatique et plus longs chemins d’un graphe. Rev Fr Autom Inf Rech Opér sér Rouge 1:127-132 · Zbl 0157.31302
[10] Vitaver LM (1962) Determination of minimal coloring of vertices of a graph by means of Boolean powers of the incidence matrix (Russian). Dokl Akad Nauk SSSR 147:758-759 · Zbl 0126.39302
[11] Yang A, Yuan J (2006) Partition the vertices of a graph into one independent set and one acyclic set. Discret Math 306:1207-1216 · Zbl 1093.05044
[12] Zaker M (2008) New bounds for the chromatic number of graphs. J Gr Theory 58:110-122 · Zbl 1149.05018
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.