Incidence Coloring Game and Arboricity of Graphs

DOI10.1007/978-3-642-45278-9_10MaRDI QIDQ2870020zbMATH OpenOpenAlexFDO

Authors Clément Charpentier, Éric Sopena

Publication date 17 January 2014

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.0166

zbMATH Keywords

arboricityincidence coloringincidence coloring gameincidence game chromatic number

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: An incidence of a graph $G$ is a pair $(v,e)$ where $v$ is a vertex of $G$ and $e$ an edge incident to $v$. Two incidences $(v,e)$ and $(w,f)$ are adjacent whenever $v=w$, or $e=f$, or $vw=e$ or $f$. The incidence coloring game [S.D. Andres, The incidence game chromatic number, Discrete Appl. Math. 157 (2009), 1980-1987] is a variation of the ordinary coloring game where the two players, Alice and Bob, alternately color the incidences of a graph, using a given number of colors, in such a way that adjacent incidences get distinct colors. If the whole graph is colored then Alice wins the game otherwise Bob wins the game. The incidence game chromatic number $i_g(G)$ of a graph $G$ is the minimum number of colors for which Alice has a winning strategy when playing the incidence coloring game on $G$. Andres proved that %$lceil3/2Delta(G)ceille$i_g(G) le 2Delta(G) + 4k - 2$forevery$k$-degenerategraph$G$.\mathrm{\%}Thearboricity$a(G)$ofagraph$G$istheminimumnumberofforestsintowhichitssetofedgescanbepartitioned.\mathrm{\%}If$G$is$k$-degenerate,then$a(G) le k le 2a(G) - 1$.Weshowinthispaperthat$i_g(G) le lfloorfrac{3Delta(G) - a(G)}{2} floor + 8a(G) - 2$foreverygraph$G$,where$a(G)$standsforthearboricityof$G$,thusimprovingtheboundgivenbyAndressince$a(G) le k$forevery$k$-degenerategraph$G$.Sincethereexistsgraphswith$i_g(G) ge lceilfrac{3Delta(G)}{2} ceil$, the multiplicative constant of our bound is best possible.

Recommendations

• The Stability Theory of Charge Distributions on Conductors
• A variational proof of Thomson's theorem
• Discrete charges on a two-dimensional conductor
• On the distribution of weighted extremal points on a surface in \(\mathbb R^d\), \(d \geqslant 3\)
• An application of Thomson s theorem to the determination of induced charge density

Cited in

(8)

• The incidence game chromatic number of \((a,d)\)-decomposable graphs
• On game chromatic vertex-critical graphs
• The game of arboricity
• Discrete charges on a two-dimensional conductor
• Some results on incidence coloring, star arboricity and domination number
• The game of arboricity
• The incidence game chromatic number of paths and subgraphs of wheels
• The incidence game chromatic number

This page was built for publication: Incidence Coloring Game and Arboricity of Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2870020)