**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Cubic graph

Summary

In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words, a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs.
A bicubic graph is a cubic bipartite graph.
In 1932, Ronald M. Foster began collecting examples of cubic symmetric graphs, forming the start of the Foster census. Many well-known individual graphs are cubic and symmetric, including the utility graph, the Petersen graph, the Heawood graph, the Möbius–Kantor graph, the Pappus graph, the Desargues graph, the Nauru graph, the Coxeter graph, the Tutte–Coxeter graph, the Dyck graph, the Foster graph and the Biggs–Smith graph. W. T. Tutte classified the symmetric cubic graphs by the smallest integer number s such that each two oriented paths of length s can be mapped to each other by exactly one symmetry of the graph. He showed that s is at most 5, and provided examples of graphs with each possible value of s from 1 to 5.
Semi-symmetric cubic graphs include the Gray graph (the smallest semi-symmetric cubic graph), the Ljubljana graph, and the Tutte 12-cage.
The Frucht graph is one of the five smallest cubic graphs without any symmetries: it possesses only a single graph automorphism, the identity automorphism.
According to Brooks' theorem every connected cubic graph other than the complete graph K4 has a vertex coloring with at most three colors. Therefore, every connected cubic graph other than K4 has an independent set of at least n/3 vertices, where n is the number of vertices in the graph: for instance, the largest color class in a 3-coloring has at least this many vertices.
According to Vizing's theorem every cubic graph needs either three or four colors for an edge coloring. A 3-edge-coloring is known as a Tait coloring, and forms a partition of the edges of the graph into three perfect matchings. By Kőnig's line coloring theorem every bicubic graph has a Tait coloring.
The bridgeless cubic graphs that do not have a Tait coloring are known as snarks.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related courses (7)

Related concepts (57)

MATH-360: Graph theory

The course aims to introduce the basic concepts and results of modern Graph Theory with special emphasis on those topics and techniques that have proved to be applicable in theoretical computer scienc

PHYS-512: Statistical physics of computation

This course covers the statistical physics approach to computer science problems ranging from graph theory and constraint satisfaction to inference and machine learning. In particular the replica and

MATH-335: Coxeter groups

Study groups generated by reflections

Symmetric graph

In the mathematical field of graph theory, a graph G is symmetric (or arc-transitive) if, given any two pairs of adjacent vertices u_1—v_1 and u_2—v_2 of G, there is an automorphism such that and In other words, a graph is symmetric if its automorphism group acts transitively on ordered pairs of adjacent vertices (that is, upon edges considered as having a direction). Such a graph is sometimes also called 1-arc-transitive or flag-transitive. By definition (ignoring u_1 and u_2), a symmetric graph without isolated vertices must also be vertex-transitive.

Edge coloring

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors.

Snark (graph theory)

In the mathematical field of graph theory, a snark is an undirected graph with exactly three edges per vertex whose edges cannot be colored with only three colors. In order to avoid trivial cases, snarks are often restricted to have additional requirements on their connectivity and on the length of their cycles. Infinitely many snarks exist. One of the equivalent forms of the four color theorem is that every snark is a non-planar graph. Research on snarks originated in Peter G.

Related lectures (43)

Social Cognition

Delves into social cognition, collaborative learning effectiveness, group consensus, and the role of technology in enhancing interactions.

Information Theory: Basics

Covers the basics of information theory, entropy, and fixed points in graph colorings and the Ising model.

Graph-to-Graph Transformers: Syntax-aware Graph Encoding

Introduces the Syntax-aware Graph-to-Graph Transformer architecture for effective conditioning on syntactic dependency graphs.