The incidence game chromatic number of (a,d)-decomposable graphs

The incidence coloring game has been introduced in Andres (2009) [2] as a variation of the ordinary coloring game. The incidence game chromatic number ι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. In Charpenti...

Full description

Saved in:
Bibliographic Details
Published in:Journal of discrete algorithms (Amsterdam, Netherlands) Netherlands), 2015-03, Vol.31, p.14-25
Main Authors: Charpentier, C., Sopena, É.
Format: Article
Language:English
Subjects:
[formula omitted]-decomposable graphs
Arboricity
Computer Science
Discrete Mathematics
Incidence coloring
Incidence coloring game
Incidence game chromatic number
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c401t-43d69e69fb3916153fe063b42e84c1b3bcb65fe53c05bf68d972f84b5d1d0cfd3
cites cdi_FETCH-LOGICAL-c401t-43d69e69fb3916153fe063b42e84c1b3bcb65fe53c05bf68d972f84b5d1d0cfd3
container_end_page 25
container_issue
container_start_page 14
container_title Journal of discrete algorithms (Amsterdam, Netherlands)
container_volume 31
creator Charpentier, C.
Sopena, É.
description The incidence coloring game has been introduced in Andres (2009) [2] as a variation of the ordinary coloring game. The incidence game chromatic number ι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. In Charpentier and Sopena (2013) [7], we proved that ιg(G)≤⌊3Δ(G)−a2⌋+8a−1 for every graph G with arboricity at most a. In this paper, we extend our previous result to (a,d)-decomposable graphs – that is graphs whose set of edges can be partitioned into two parts, one inducing a graph with arboricity at most a, the other inducing a graph with maximum degree at most d – and prove that ιg(G)≤⌊3Δ(G)−a2⌋+8a+3d−1 for every (a,d)-decomposable graph G.
doi_str_mv 10.1016/j.jda.2014.10.001
format article
fullrecord <record><control><sourceid>hal_cross</sourceid><recordid>TN_cdi_hal_primary_oai_HAL_hal_02264654v1</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>S1570866714000690</els_id><sourcerecordid>oai_HAL_hal_02264654v1</sourcerecordid><originalsourceid>FETCH-LOGICAL-c401t-43d69e69fb3916153fe063b42e84c1b3bcb65fe53c05bf68d972f84b5d1d0cfd3</originalsourceid><addsrcrecordid>eNp9kE1Lw0AQhhdRsFZ_gLccLZi4k-xuErxYilqh4KWel_2YNRuapuzWgv--CZUePc0H7zMwDyH3QDOgIJ7arLUqyymwYc4ohQsyAV7StBIlvzz3orwmNzG2lOYcWD4hL-sGE7813uLWYPKtOkxME_pO7b1Jtj-dxpD0LnlQj3aWWjR9t-uj0pshG9SuibfkyqlNxLu_OiVfb6_rxTJdfb5_LOar1DAK-5QVVtQoaqeLGgTwwiEVhWY5VsyALrTRgjvkhaFcO1HZusxdxTS3YKlxtpiS2eluozZyF3ynwq_slZfL-UqOO5rnggnODjBk4ZQ1oY8xoDsDQOWoS7Zy0CVHXeNq0DUwzycGhycOHoOMxo9OrA9o9tL2_h_6CHJBcQ4</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>The incidence game chromatic number of (a,d)-decomposable graphs</title><source>ScienceDirect Freedom Collection</source><creator>Charpentier, C. ; Sopena, É.</creator><creatorcontrib>Charpentier, C. ; Sopena, É.</creatorcontrib><description>The incidence coloring game has been introduced in Andres (2009) [2] as a variation of the ordinary coloring game. The incidence game chromatic number ι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. In Charpentier and Sopena (2013) [7], we proved that ιg(G)≤⌊3Δ(G)−a2⌋+8a−1 for every graph G with arboricity at most a. In this paper, we extend our previous result to (a,d)-decomposable graphs – that is graphs whose set of edges can be partitioned into two parts, one inducing a graph with arboricity at most a, the other inducing a graph with maximum degree at most d – and prove that ιg(G)≤⌊3Δ(G)−a2⌋+8a+3d−1 for every (a,d)-decomposable graph G.</description><identifier>ISSN: 1570-8667</identifier><identifier>EISSN: 1570-8675</identifier><identifier>DOI: 10.1016/j.jda.2014.10.001</identifier><language>eng</language><publisher>Elsevier B.V</publisher><subject>[formula omitted]-decomposable graphs ; Arboricity ; Computer Science ; Discrete Mathematics ; Incidence coloring ; Incidence coloring game ; Incidence game chromatic number</subject><ispartof>Journal of discrete algorithms (Amsterdam, Netherlands), 2015-03, Vol.31, p.14-25</ispartof><rights>2014 Elsevier B.V.</rights><rights>Distributed under a Creative Commons Attribution 4.0 International License</rights><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c401t-43d69e69fb3916153fe063b42e84c1b3bcb65fe53c05bf68d972f84b5d1d0cfd3</citedby><cites>FETCH-LOGICAL-c401t-43d69e69fb3916153fe063b42e84c1b3bcb65fe53c05bf68d972f84b5d1d0cfd3</cites><orcidid>0000-0002-9570-1840</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>230,314,780,784,885,27924,27925</link.rule.ids><backlink>$$Uhttps://hal.science/hal-02264654$$DView record in HAL$$Hfree_for_read</backlink></links><search><creatorcontrib>Charpentier, C.</creatorcontrib><creatorcontrib>Sopena, É.</creatorcontrib><title>The incidence game chromatic number of (a,d)-decomposable graphs</title><title>Journal of discrete algorithms (Amsterdam, Netherlands)</title><description>The incidence coloring game has been introduced in Andres (2009) [2] as a variation of the ordinary coloring game. The incidence game chromatic number ι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. In Charpentier and Sopena (2013) [7], we proved that ιg(G)≤⌊3Δ(G)−a2⌋+8a−1 for every graph G with arboricity at most a. In this paper, we extend our previous result to (a,d)-decomposable graphs – that is graphs whose set of edges can be partitioned into two parts, one inducing a graph with arboricity at most a, the other inducing a graph with maximum degree at most d – and prove that ιg(G)≤⌊3Δ(G)−a2⌋+8a+3d−1 for every (a,d)-decomposable graph G.</description><subject>[formula omitted]-decomposable graphs</subject><subject>Arboricity</subject><subject>Computer Science</subject><subject>Discrete Mathematics</subject><subject>Incidence coloring</subject><subject>Incidence coloring game</subject><subject>Incidence game chromatic number</subject><issn>1570-8667</issn><issn>1570-8675</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2015</creationdate><recordtype>article</recordtype><recordid>eNp9kE1Lw0AQhhdRsFZ_gLccLZi4k-xuErxYilqh4KWel_2YNRuapuzWgv--CZUePc0H7zMwDyH3QDOgIJ7arLUqyymwYc4ohQsyAV7StBIlvzz3orwmNzG2lOYcWD4hL-sGE7813uLWYPKtOkxME_pO7b1Jtj-dxpD0LnlQj3aWWjR9t-uj0pshG9SuibfkyqlNxLu_OiVfb6_rxTJdfb5_LOar1DAK-5QVVtQoaqeLGgTwwiEVhWY5VsyALrTRgjvkhaFcO1HZusxdxTS3YKlxtpiS2eluozZyF3ynwq_slZfL-UqOO5rnggnODjBk4ZQ1oY8xoDsDQOWoS7Zy0CVHXeNq0DUwzycGhycOHoOMxo9OrA9o9tL2_h_6CHJBcQ4</recordid><startdate>20150301</startdate><enddate>20150301</enddate><creator>Charpentier, C.</creator><creator>Sopena, É.</creator><general>Elsevier B.V</general><general>Elsevier</general><scope>6I.</scope><scope>AAFTH</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>1XC</scope><orcidid>https://orcid.org/0000-0002-9570-1840</orcidid></search><sort><creationdate>20150301</creationdate><title>The incidence game chromatic number of (a,d)-decomposable graphs</title><author>Charpentier, C. ; Sopena, É.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c401t-43d69e69fb3916153fe063b42e84c1b3bcb65fe53c05bf68d972f84b5d1d0cfd3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2015</creationdate><topic>[formula omitted]-decomposable graphs</topic><topic>Arboricity</topic><topic>Computer Science</topic><topic>Discrete Mathematics</topic><topic>Incidence coloring</topic><topic>Incidence coloring game</topic><topic>Incidence game chromatic number</topic><toplevel>online_resources</toplevel><creatorcontrib>Charpentier, C.</creatorcontrib><creatorcontrib>Sopena, É.</creatorcontrib><collection>ScienceDirect Open Access Titles</collection><collection>Elsevier:ScienceDirect:Open Access</collection><collection>CrossRef</collection><collection>Hyper Article en Ligne (HAL)</collection><jtitle>Journal of discrete algorithms (Amsterdam, Netherlands)</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Charpentier, C.</au><au>Sopena, É.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>The incidence game chromatic number of (a,d)-decomposable graphs</atitle><jtitle>Journal of discrete algorithms (Amsterdam, Netherlands)</jtitle><date>2015-03-01</date><risdate>2015</risdate><volume>31</volume><spage>14</spage><epage>25</epage><pages>14-25</pages><issn>1570-8667</issn><eissn>1570-8675</eissn><abstract>The incidence coloring game has been introduced in Andres (2009) [2] as a variation of the ordinary coloring game. The incidence game chromatic number ι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. In Charpentier and Sopena (2013) [7], we proved that ιg(G)≤⌊3Δ(G)−a2⌋+8a−1 for every graph G with arboricity at most a. In this paper, we extend our previous result to (a,d)-decomposable graphs – that is graphs whose set of edges can be partitioned into two parts, one inducing a graph with arboricity at most a, the other inducing a graph with maximum degree at most d – and prove that ιg(G)≤⌊3Δ(G)−a2⌋+8a+3d−1 for every (a,d)-decomposable graph G.</abstract><pub>Elsevier B.V</pub><doi>10.1016/j.jda.2014.10.001</doi><tpages>12</tpages><orcidid>https://orcid.org/0000-0002-9570-1840</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 1570-8667
ispartof Journal of discrete algorithms (Amsterdam, Netherlands), 2015-03, Vol.31, p.14-25
issn 1570-8667
1570-8675
language eng
recordid cdi_hal_primary_oai_HAL_hal_02264654v1
source ScienceDirect Freedom Collection
subjects [formula omitted]-decomposable graphs
Arboricity
Computer Science
Discrete Mathematics
Incidence coloring
Incidence coloring game
Incidence game chromatic number
title The incidence game chromatic number of (a,d)-decomposable graphs
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-04T23%3A55%3A16IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-hal_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=The%20incidence%20game%20chromatic%20number%20of%20(a,d)-decomposable%20graphs&rft.jtitle=Journal%20of%20discrete%20algorithms%20(Amsterdam,%20Netherlands)&rft.au=Charpentier,%20C.&rft.date=2015-03-01&rft.volume=31&rft.spage=14&rft.epage=25&rft.pages=14-25&rft.issn=1570-8667&rft.eissn=1570-8675&rft_id=info:doi/10.1016/j.jda.2014.10.001&rft_dat=%3Chal_cross%3Eoai_HAL_hal_02264654v1%3C/hal_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c401t-43d69e69fb3916153fe063b42e84c1b3bcb65fe53c05bf68d972f84b5d1d0cfd3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true