Pushpa Publishing House

Journal Menu

Content

Volume 42 (2025)

Volume 41 (2024)

Volume 40 (2023)

Volume 39 (2023)

Volume 38 (2023)

Volume 29 (2022)

Volume 28 (2021)

Volume 27 (2021)

Volume 26 (2021)

Volume 25 (2020)

Volume 24 (2020)

Volume 23 (2020)

Volume 22 (2019)

Volume 21 (2019)

Volume 20 (2019)

Volume 19 (2018)

Volume 18 (2017)

Volume 17 (2016)

Volume 16 (2015)

Volume 15 (2015)

Volume 14 (2014)

Volume 13 (2014)

Volume 12 (2013)

Volume 11 (2013)

Volume 10 (2012)

Volume 7 (2011)

Volume 6 (2010)

Volume 5 (2010)

Volume 4 (2009)

Volume 3 (2009)

Volume 2 (2008)

	Volume 2, Issue 2 Pg 85 - 163 (October 2008)
	Volume 2, Issue 1 Pg 1 - 84 (July 2008)

Volume 1 (2008)

-->

Advances and Applications in Discrete Mathematics

that are either 4-edge colourable or a 4-edge colouring assignment exists for most of their edges is an interesting challenge. One parameter to categorize these graphs is the distance between vertices of degree 4. Using this parameter the following result is getting: A planar connected and bridgeless graph G, with

and

having vertices of degree 4 whose distance is at least 5, is in Class 1. A second result comes as a consequence of the first one providing us by a procedure to assign a 4-edge colouring to “almost all” the edges of a 4-regular planar graph, with “large” girth. Actually we prove that: A connected bridgeless and planar 4-regular graph G, with girth

has a 4-edge colouring in

edges, where n is the order of G. Therefore, the fraction of the number of the edges which get a 4-colouring to the size of G is at least

Advances and Applications in Discrete Mathematics
Volume 2, Issue 2, Pages 97 - 102 (October 2008)

ON 4-EDGE COLOURING PLANAR BRIDGELESS GRAPHS WITH LARGE GIRTH
Diamantis Koreas (Greece)

Abstract:
Planar graphs with maximum degree 4 are either in Class 1 or in Class 2. The question if the problem to decide whether these graphs belong to one of these classes is NP-complete remains open. A probable answer is “yes”. Therefore, finding categories of planar graphs with

and

has a 4-edge colouring in

edges, where n is the order of G. Therefore, the fraction of the number of the edges which get a 4-colouring to the size of G is at least

Keywords and phrases: edge-colouring, 2-factors, NP-complete problems.

Number of Downloads: 335 | Number of Views: 869