The size of graphs with clique number m and without nowhere-zero 4-flows

Zhi-Hong Chen

doi:10.1016/0012-365X(95)00341-S

The size of graphs with clique number m and without nowhere-zero 4-flows

Zhi-Hong Chen

Butler University

Research output: Contribution to journal › Article › peer-review

Abstract

<div class="line" id="line-25"> <span style='color: rgb(46, 46, 46); font-family: NexusSerif, Georgia, "Times New Roman", Times, STIXGeneral, "Cambria Math", "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", "Arial Unicode MS", serif; font-size: 18px;'> Let  </span> <i style='color: rgb(46, 46, 46); font-family: NexusSerif, Georgia, "Times New Roman", Times, STIXGeneral, "Cambria Math", "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", "Arial Unicode MS", serif; font-size: 18px;'> G </i> <span style='color: rgb(46, 46, 46); font-family: NexusSerif, Georgia, "Times New Roman", Times, STIXGeneral, "Cambria Math", "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", "Arial Unicode MS", serif; font-size: 18px;'>  be a 2-edge-connected simple graph on  </span> <i style='color: rgb(46, 46, 46); font-family: NexusSerif, Georgia, "Times New Roman", Times, STIXGeneral, "Cambria Math", "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", "Arial Unicode MS", serif; font-size: 18px;'> n </i> <span style='color: rgb(46, 46, 46); font-family: NexusSerif, Georgia, "Times New Roman", Times, STIXGeneral, "Cambria Math", "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", "Arial Unicode MS", serif; font-size: 18px;'> &ges;24 vertices containng no  </span> <i style='color: rgb(46, 46, 46); font-family: NexusSerif, Georgia, "Times New Roman", Times, STIXGeneral, "Cambria Math", "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", "Arial Unicode MS", serif; font-size: 18px;'> K </i> <i> <span style='color: rgb(46, 46, 46); font-family: NexusSerif, Georgia, "Times New Roman", Times, STIXGeneral, "Cambria Math", "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", "Arial Unicode MS", serif; font-size: 13.5px;'> m </span> </i> <span style='color: rgb(46, 46, 46); font-family: NexusSerif, Georgia, "Times New Roman", Times, STIXGeneral, "Cambria Math", "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", "Arial Unicode MS", serif; font-size: 18px;'> +1. Of </span></div><div class="line" id="line-327"> <br/></div><div class="line" id="line-302"> <span style='color: rgb(46, 46, 46); font-family: NexusSerif, Georgia, "Times New Roman", Times, STIXGeneral, "Cambria Math", "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", "Arial Unicode MS", serif; font-size: 16.2px;'> |E(G)|&ges;(n - 17 - k2)+(m - l)(k + 12)+ 33, </span></div><div class="line" id="line-324"> <br/></div><div class="line" id="line-314"> <span style='color: rgb(46, 46, 46); font-family: NexusSerif, Georgia, "Times New Roman", Times, STIXGeneral, "Cambria Math", "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", "Arial Unicode MS", serif; font-size: 18px;'> where &lfloor; </span> <i style='color: rgb(46, 46, 46); font-family: NexusSerif, Georgia, "Times New Roman", Times, STIXGeneral, "Cambria Math", "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", "Arial Unicode MS", serif; font-size: 18px;'> n </i> <span style='color: rgb(46, 46, 46); font-family: NexusSerif, Georgia, "Times New Roman", Times, STIXGeneral, "Cambria Math", "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", "Arial Unicode MS", serif; font-size: 18px;'> −17/ </span> <i style='color: rgb(46, 46, 46); font-family: NexusSerif, Georgia, "Times New Roman", Times, STIXGeneral, "Cambria Math", "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", "Arial Unicode MS", serif; font-size: 18px;'> m </i> <span style='color: rgb(46, 46, 46); font-family: NexusSerif, Georgia, "Times New Roman", Times, STIXGeneral, "Cambria Math", "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", "Arial Unicode MS", serif; font-size: 18px;'> &rfloor;, then either  </span> <i style='color: rgb(46, 46, 46); font-family: NexusSerif, Georgia, "Times New Roman", Times, STIXGeneral, "Cambria Math", "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", "Arial Unicode MS", serif; font-size: 18px;'> G </i> <span style='color: rgb(46, 46, 46); font-family: NexusSerif, Georgia, "Times New Roman", Times, STIXGeneral, "Cambria Math", "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", "Arial Unicode MS", serif; font-size: 18px;'>  has a nowhere-zero 4-flow, or  </span> <i style='color: rgb(46, 46, 46); font-family: NexusSerif, Georgia, "Times New Roman", Times, STIXGeneral, "Cambria Math", "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", "Arial Unicode MS", serif; font-size: 18px;'> G </i> <span style='color: rgb(46, 46, 46); font-family: NexusSerif, Georgia, "Times New Roman", Times, STIXGeneral, "Cambria Math", "Lucida Sans Unicode", "Microsoft Sans Serif", "Segoe UI Symbol", "Arial Unicode MS", serif; font-size: 18px;'>  can be contracted to the Petersen graph. This is a generalization of a result in [4]. </span></div>

Original language	American English
Journal	Discrete Mathematics
Volume	163
Issue number	1-3
DOIs	https://doi.org/10.1016/0012-365X(95)00341-S
State	Published - Jan 1997

Keywords

Computer science
Graph theory
Mathematics

Disciplines

Computer Sciences
Mathematics

Access to Document

10.1016/0012-365X(95)00341-SLicense: Unspecified

Cite this

@article{6e4b4e5ee9b44598a416899e4599d927,

title = "The size of graphs with clique number m and without nowhere-zero 4-flows",

abstract = " Let  G  be a 2-edge-connected simple graph on  n &ges;24 vertices containng no  K m +1. Of |E(G)|&ges;(n - 17 - k2)+(m - l)(k + 12)+ 33, where &lfloor; n −17/ m &rfloor;, then either  G  has a nowhere-zero 4-flow, or  G  can be contracted to the Petersen graph. This is a generalization of a result in [4]. ",

keywords = "Computer science, Graph theory, Mathematics",

author = "Zhi-Hong Chen",

note = "Get this from a library! The size of graphs with clique number m and without nowhere-zero 4-flows. [Z -H Chen]",

year = "1997",

month = jan,

doi = "10.1016/0012-365X(95)00341-S",

language = "American English",

volume = "163",

journal = "Discrete Mathematics",

issn = "0012-365X",

number = "1-3",

}

TY - JOUR

T1 - The size of graphs with clique number m and without nowhere-zero 4-flows

AU - Chen, Zhi-Hong

N1 - Get this from a library! The size of graphs with clique number m and without nowhere-zero 4-flows. [Z -H Chen]

PY - 1997/1

Y1 - 1997/1

N2 - Let  G  be a 2-edge-connected simple graph on  n &ges;24 vertices containng no  K m +1. Of |E(G)|&ges;(n - 17 - k2)+(m - l)(k + 12)+ 33, where &lfloor; n −17/ m &rfloor;, then either  G  has a nowhere-zero 4-flow, or  G  can be contracted to the Petersen graph. This is a generalization of a result in [4].

AB - Let  G  be a 2-edge-connected simple graph on  n &ges;24 vertices containng no  K m +1. Of |E(G)|&ges;(n - 17 - k2)+(m - l)(k + 12)+ 33, where &lfloor; n −17/ m &rfloor;, then either  G  has a nowhere-zero 4-flow, or  G  can be contracted to the Petersen graph. This is a generalization of a result in [4].

KW - Computer science

KW - Graph theory

KW - Mathematics

UR - http://www.worldcat.org/oclc/207810319

U2 - 10.1016/0012-365X(95)00341-S

DO - 10.1016/0012-365X(95)00341-S

M3 - Article

SN - 0012-365X

VL - 163

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

The size of graphs with clique number m and without nowhere-zero 4-flows

Abstract

Keywords

Disciplines

Access to Document

Other files and links

Cite this