Search

The paper designs five graph operations, and proves that every signed graph with chromatic number q , defined by Kang and Steffen (in press), can be obtained from copies of the all-positive complete graph ( K q , + ) by repeatedly applying these operations. This result gives a signed version of the Hajós theorem, emphasizing the role of all-positive complete graphs in the class of signed graphs, as in the class of unsigned graphs. Moreover, a similar result is established for the signed chromatic number defined by Máčajová, Raspaud and Škoviera. [ABSTRACT FROM AUTHOR]

The chromatic number χ ( ( G , σ ) ) of a signed graph ( G , σ ) is the smallest number k for which there is a function c : V ( G ) → Z k such that c ( v ) ≠ σ ( e ) c ( w ) for every edge e = v w . Let Σ ( G ) be the set of all signatures of G . We study the chromatic spectrum Σ χ ( G ) = { χ ( ( G , σ ) ) : σ ∈ Σ ( G ) } of ( G , σ ) . Let M χ ( G ) = max { χ ( ( G , σ ) ) : σ ∈ Σ ( G ) } , and m χ ( G ) = min { χ ( ( G , σ ) ) : σ ∈ Σ ( G ) } . We show that Σ χ ( G ) = { k : m χ ( G ) ≤ k ≤ M χ ( G ) } . We also prove some basic facts for critical graphs. Analogous results are obtained for a notion of vertex-coloring of signed graphs which was introduced by Máčajová, Raspaud, and Škoviera in Máčajová et al. (2016). [ABSTRACT FROM AUTHOR]

In this paper, we prove that planar graphs without cycles of length 4, 6, 9 are 3-colorable. [ABSTRACT FROM AUTHOR]

Montassier et al. showed that every planar graph without cycles of length at most five at distance less than four is 3-colorable [A relaxation of of Havel's 3-color problem, Inform. Process. Lett. 107 () 107-109]. Borodin, Montassier and Raspaud asked in [Planar graphs without adjacent cycles of length at most seven are 3-colorable, Discrete Math. 310 () 167-173]: is every planar graph without adjacent cycles of length at most five 3-colorable? In this note, we show that every planar graph without cycles of length at most five at distance less than two is 3-colorable. [ABSTRACT FROM AUTHOR]

In a proper edge-coloring of a cubic graph, an edge e is normal if the set of colors used by the five edges incident with an end of e has cardinality 3 or 5. The Petersen coloring conjecture asserts that every bridgeless cubic graph has a normal 5-edge-coloring, that is, a proper 5-edge-coloring such that all edges are normal. In this paper, we prove a result related to the Petersen coloring conjecture. The parameter μ 3 is a measurement for cubic graphs, introduced by Steffen in 2015. Our result shows that every bridgeless cubic graph G has a proper 5-edge-coloring such that at least | E (G) | − μ 3 (G) (which is no less than 27 35 | E (G) |) edges are normal. This result improves on some earlier results of Bílková and Šámal. [ABSTRACT FROM AUTHOR]