Fractional balanced chromatic number of signed subcubic graphs
Preprint
Abstract
A signed graph is a pair $(G,σ)$, where $G$ is a graph and $σ: E(G)\rightarrow \{-, +\}$, called signature, is an assignment of signs to the edges. Given a signed graph $(G,σ)$ with no negative loops, a balanced $(p,q)$-coloring of $(G,σ)$ is an assignment $f$ of $q$ colors to each vertex from a pool of $p$ colors such that each color class induces a balanced subgraph, i.e., no negative cycles. Let $(K_4,-)$ be the signed graph on $K_4$ with all edges being negative. In this work, we show that every signed (simple) subcubic graph admits a balanced $(5,3)$-coloring except for $(K_4,-)$ and signed graphs switching equivalent to it. For this particular signed graph the best balanced colorings are $(2p,p)$-colorings.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- The fractional chromatic number of triangle-free subcubic graphsEuropean Journal of Combinatorics, 2013
- Subcubic triangle-free graphs have fractional chromatic number at most 14/52013
- The fractional chromatic number of triangle-free graphs withDiscrete Mathematics, 2012
- Fractional colorings of cubic graphs with large girthSIAM Journal on Discrete Mathematics, 2011
- The Fractional Chromatic Number of Graphs of Maximum Degree at Most ThreeSIAM Journal on Discrete Mathematics, 2010
- Independent sets in triangle-free cubic planar graphsJournal of Combinatorial Theory, Series B, 2006
- A new proof of the independence ratio of triangle-free cubic graphsDiscrete Mathematics, 2001
- Edge density and independence ratio in triangle-free graphs with maximum degree threeDiscrete Mathematics, 1996
- Balanced decompositions of a signed graphJournal of Combinatorial Theory, Series B, 1987
- A (<5)-Colour Theorem for Planar GraphsBulletin of the London Mathematical Society, 1973